package com;

import java.util.Collection;
import java.util.Map;
import java.util.Set;

/**
 * 红黑树
 */
public class RedBlackTree<Key extends Comparable<Key>, Val> implements Map<Key, Val> {

    public static final boolean RED = true;

    public static final boolean BLACK = false;

    public static class Node<Key, Val> {
        Key key;
        Val val;

        Node<Key, Val> left;

        Node<Key, Val> right;

        int N;
        boolean color;
    }


    /**
     * 左旋了之后会变成黑色节点
     * 把右链接是红色链接（3-节点）中，较大的key作为根节点
     * @param node
     * @return
     */
    private Node<Key, Val> rotateLeft(Node<Key, Val> node) {
        if (node.right == null) {
            return node;
        }
        if (!this.isRed(node.right)) {
            return node;
        }
//        该节点的右节点为红色节点，左旋了之后会变成黑色节点
        Node<Key, Val> onceRedNode = node.right;
//      将当前节点的右链接替换为红色节点的左链接
        node.right = onceRedNode.left;
//      将红色节点的左链接指向当前节点
        onceRedNode.left = node;
//        自旋完成，改变节点的颜色
        onceRedNode.color = node.color;
        node.color = RED;
        onceRedNode.N = node.N;
        node.N = 1 + size(node.left) + size(node.right);
//        此时曾经的父节点变成了红色节点，而曾经的红色节点变成了 3-节点中大的key，返回值将用于重置父节点中相应的链接
        return onceRedNode;
    }

    /**
     * 右旋
     * @param node
     * @return
     */
    private Node<Key, Val> rotateRight(Node<Key, Val> node) {
        if (node.left == null) {
            return node;
        }
        if (!this.isRed(node.left)) {
            return node;
        }
//        该节点的左节点为红色节点，右旋了之后会变成黑色节点
        Node<Key, Val> onceRedNode = node.left;
//      将当前节点的左链接替换为红色节点的右链接
        node.left = onceRedNode.right;
//      将红色节点的右链接指向当前节点
        onceRedNode.right = node;
//        自旋完成，改变节点的颜色
        onceRedNode.color = node.color;
        node.color = RED;
        onceRedNode.N = node.N;
        node.N = 1 + size(node.left) + size(node.right);
        return onceRedNode;
    }

    private boolean isRed(Node<Key, Val> node) {
        return node.color == RED;
    }

    @Override
    public int size() {
        return 0;
    }

    public int size(Node<Key, Val> node) {
        if (node == null) {

            return 0;
        }
        return node.N;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public boolean containsKey(Object key) {
        return false;
    }

    @Override
    public boolean containsValue(Object value) {
        return false;
    }

    @Override
    public Val get(Object key) {
        return null;
    }

    @Override
    public Val put(Key key, Val value) {
        return null;
    }

    @Override
    public Val remove(Object key) {
        return null;
    }

    @Override
    public void putAll(Map<? extends Key, ? extends Val> m) {

    }

    @Override
    public void clear() {

    }

    @Override
    public Set<Key> keySet() {
        return null;
    }

    @Override
    public Collection<Val> values() {
        return null;
    }

    @Override
    public Set<Entry<Key, Val>> entrySet() {
        return null;
    }


}
